package LinkedList;
/**
*User:浪尘
*Date:2022-09-18
*Time:10:21
*/
//将数据元素通过节点进行存储，然后使用一个叫做next的引用/指针将这些节点串联起来，这样的结构我们把它叫做链表。
public class MySingleList {

    /**
     * 节点内部类
     */
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;

        }
    }

    public ListNode head;//不初始化了 默认就是null

    public void createList() {//最简单的方式 穷举
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(12);
        ListNode listNode3 = new ListNode(12);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);
        this.head = listNode1;
        listNode1.next = listNode2;//当前节点存储下一个元素的地址
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
    }

    /**
     * 打印链表里面的数据
     */
    public void display() {
        ListNode cur = this.head;//head不变 让我们的头结点不变 cur去变
        while (cur != null) {
            /**
             为什么是判断cur不等于空 而不是判断cur.next不为空
             结合平板里面的截图看 就是当下一个节点是null的时候
            我们可以打印出最后一个元素 否则提前判断 不能遍历到最后一个元素
            */
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }


    //得到单链表的长度
    public int size(){
        ListNode cur = this.head;
        int count =0;
        while(cur!=null){//可不敢写成cur.next！=null 如果链表为空的话 那么cur.next就会发生空指针异常 报错
            count++;
            cur = cur.next;
        }
        return count;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }


    //头插法
    public void addFirst(int data){
        //当你在链表当中插入一个数据的时候 一点要记住 先去绑定后面的节点
        //比起顺序表的好处就是 1：插入数的时候不用挪动元素 2：只需要修改指向即可。时间复杂度是O(1)
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }


    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null){
            this.head = node;
        }else{
            while(cur.next!= null){
                cur = cur.next;
            }
            //走到这个时候已经找到尾巴了
            cur.next = node;
        }
    }


    /**
     * 任意位置插入,第一个数据节点为0号下标
     * @param index
     * @param data
     */
    public void addIndex(int index,int data){
        if(index<0 || index>size()){
            System.out.println("index位置不合法！");
            throw new IndexWrongFulException("index位置不合法！");
        }
        if(index == 0){//相当于头插法
            addFirst(data);
            return;
        }
        if(index == size()) {//相当于尾插法
            addLast(data);
            return;
        }
        //1.先走index-1步 找到cur
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //2.修改指向
        node.next = cur.next;
        cur.next = node;
    }
    private ListNode findIndexSubOne(int index){
        //定义成private本来就是想只提供给我这个任意位置的插入的函数使用
        // 不想让类外的函数等访问
        ListNode cur = this.head;
        while(index-1!=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }


    /**
     * 删除第一次出现关键字为key的节点
     * @param key
     */
    public void remove(int key){
         if(this.head == null){//头结点就是空
            return;
         }
        if(this.head.val == key){//删除头结点
            this.head = this.head.next;
            return;
        }
        ListNode cur = findIndexSubOne(key);//找前驱
        if(cur == null){
            System.out.println("没有你要找的数字！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;//核心代码！！！
    }


    //找出现key的前驱节点 cur
    private ListNode findProverOfkey(int key){
        ListNode cur = this.head;
        while (cur.next != null){
            //为什么是cur.next 因为我们需要提前判断下一个节点
            //  如果为空 说明后面已经没有我们要找到的元素了
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;//表示没找到要删除的元素
    }


    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(this.head == null){
            return;
        }
        ListNode cur = this.head.next;
        ListNode prev = this.head;
        while (cur!=null){
           if(cur.val == key){
               prev.next = cur.next;
               cur = cur.next;
           }else{
               prev = cur;
               cur = cur.next;
           }
        }
        if(this.head.val == key){
            this.head =this.head.next;
        }
    }


    public void clear() {
        this.head = null;
    }


    /**
     * 反转链表
     * @return
     */
    public ListNode reverseList(){
        if(head == null){//没有一个节点的情况
            return null;
        }
        if(head.next == null){//只有一个节点的情况
            return head;
        }

        ListNode cur = head.next;
        head.next = null;
        while (cur!=null){
            ListNode curNext  = cur.next;
            cur.next = head;
            head =cur;
            cur = curNext;
        }
        return head;
    }

    /**
     * 寻找链表的中间节点
     * @param
     * @return
     */
    public ListNode middleNode() {//返回链表的中间结点
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    /**
     * 链表中倒数第k个结点
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode fast = this.head;
        ListNode slow = this.head;
        if(k<=0 || head == null){
            return null;
        }
        while(k-1!=0){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            k--;
        }
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        System.out.println("创造单链表");
        mySingleList.createList();
//        mySingleList.removeAllKey(12);
        mySingleList.clear();
        mySingleList.display();
        mySingleList.middleNode();
//        mySingleList.remove(12);
//        mySingleList.display();
//        System.out.println("打印单链表");
//        mySingleList.display();
//        int len = mySingleList.size();
//        System.out.println("长度为："+len);
//        boolean ex = mySingleList.contains(12);
//        System.out.println(ex);
//        mySingleList.addFirst(12);//头插法
//        mySingleList.addFirst(23);
//        mySingleList.addFirst(34);
//        mySingleList.addFirst(45);
//        mySingleList.addFirst(56);
//        mySingleList.display();
//          mySingleList.addLast(12);
//          mySingleList.addLast(23);
//          mySingleList.addLast(34);
//          mySingleList.addLast(45);
//          mySingleList.addLast(56);
//          mySingleList.display();

//        System.out.println();
//        mySingleList.addIndex(3,666);//在任意位置插入数据
//        System.out.println("任意位置插入数据：");
//        mySingleList.display();
//        mySingleList.remove(34);
//        System.out.println("任意位置插入数据后：");
//        mySingleList.display();
//        System.out.println();
//        System.out.println("链表长度为:"+mySingleList.size());
//        System.out.println("判断某个元素key是否在单链表中:"+mySingleList.contains(23));
    }
}
